package org.chengn.level_middle.context2866;

import java.util.List;
import java.util.Stack;

/**
 * @Title: Context2866
 * @Author ChengN
 * @Package org.chengn.level_middle.context2866
 * @Date 2023/12/21 1:13
 * @description: 美丽塔Ⅱ
 */
public class Context2866 {
    public long maximumSumOfHeights(List<Integer> maxHeights) {
        long[] heights = new long[maxHeights.size()];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < maxHeights.size(); ++i) {
            long val = maxHeights.get(i);
            if (stack.isEmpty() || maxHeights.get(stack.peek()) <= val) {
                heights[i] = (i == 0 ? 0 : heights[i - 1]) + val;
            } else {
                while (!stack.isEmpty() && maxHeights.get(stack.peek()) > val) {
                    stack.pop();
                }
                heights[i] = stack.isEmpty() ? (i + 1) * val : heights[stack.peek()] + (i - stack.peek()) * val;

            }
            stack.push(i);
        }


        long[] preHeights = new long[maxHeights.size()];
        Stack<Integer> preStack = new Stack<>();
        for (int i = maxHeights.size() - 1; i >= 0; --i) {
            long val = maxHeights.get(i);
            if (preStack.isEmpty() || maxHeights.get(preStack.peek()) <= val) {
                preHeights[i] = (i == maxHeights.size() - 1 ? 0 : preHeights[i + 1]) + val;
            } else {
                while (!preStack.isEmpty() && maxHeights.get(preStack.peek()) > val) {
                    preStack.pop();
                }
                preHeights[i] = preStack.isEmpty() ? (maxHeights.size() - i) * val : preHeights[preStack.peek()] + (preStack.peek() - i) * val;
            }
            preStack.push(i);
        }

        long res = -1;
        for (int i = 0; i < maxHeights.size(); ++i) {
            res = Math.max(res, heights[i] + preHeights[i] - maxHeights.get(i));
        }
        return res;
    }
}
